package mht.practice.sort;

import java.util.Arrays;

/**
 * Created by MHT on 2017/9/15.
 */
public class mht {

    public void charu(int arr[]){

        for (int i=0;i<arr.length;i++){
            for (int j=i;j>0;j--){
                if (arr[j] < arr[j-1])
                    swap(arr,j-1,j);
            }
        }
    }

    public void xuanze(int arr[]){

        for (int i=0;i<arr.length;i++){

            int index = i;
            for (int j=i+1;j<arr.length;j++){
                if (arr[j] < arr[index])
                    index = j;
            }

            swap(arr,i,index);
        }
    }

    public void maopao(int arr[]){

        boolean swapped = false;
        int n = arr.length;
        do {

            swapped = false;
            for (int i=1;i<n;i++){
                if (arr[i-1] > arr[i]){
                    swap(arr,i-1,i);
                    swapped = true;
                }
            }
            n--;
        }while (swapped);
    }


    //归并排序
    public void guibing(int arr[]){

        int n = arr.length;
        _guibing(arr,0,n-1);
    }

    public void _guibing(int arr[],int l,int r){
        if (l>=r){
            return;
        }

        int mid = l+(r-l)/2;
        _guibing(arr,l,mid);
        _guibing(arr,mid+1,r);

        if (arr[mid] > arr[mid + 1])
            merge(arr,l,mid,r);
    }

    public void merge(int arr[],int l,int mid,int r){

        int b[] = Arrays.copyOfRange(arr,l,r+1);
        int i = l;
        int j = mid + 1;


        for (int k = l; k <= r ; k++){

            if (i>mid){
                arr[k] = b[j-l];
                j++;
            } else if (j>r){
                arr[k] = b[i-l];
                i++;
            } else if (b[i-l] < b[j-l]){
                arr[k] = b[i-l];
                i++;
            } else {
                arr[k] = b[j-l];
                j++;
            }
        }
    }

    //快速排序
    public void kuaipai(int arr[]){

        int n = arr.length;
        _kuaipai(arr,0,n-1);
    }

    public void _kuaipai(int arr[],int l,int r){

        if (l>=r)
            return;

        int p = partition(arr,l,r);
        _kuaipai(arr,l,p-1);
        _kuaipai(arr,p+1,r);
    }

    public int  partition(int arr[],int l,int r){

        int x = (int)(Math.random()*(r-l+1)+l);
        swap(arr,l,x);
        int v = arr[l];


        int j = l;
        for (int i=l+1;i<=r;i++){

            if (arr[i] < v){
                j++;
                swap(arr,i,j);
            }
        }
        swap(arr,l,j);
        return j;
    }

    //双路快速排序
    public int partition2(int arr[],int l,int r){

        int x = (int)(Math.random()*(r-l+1)+l);
        swap(arr,l,x);
        int v = arr[l];

        int i=l+1;
        int j=r;
        while (true){

            while (i<=r && arr[i]<v)
                i++;
            while (j>=l+1 && arr[j]>v)
                j--;

            if (i>j)
                break;

            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }

    public void threeSort(int arr[],int l,int r){

        int x = (int)(Math.random()*(r-l+1)+l);
        swap(arr,x,l);
        int v = arr[l];

        int lt = l;
        int i = l+1;
        int gt = r+1;

        while (i<gt){

            if (arr[i]<v){
                swap(arr,i,lt+1);
                lt++;
                i++;
            }else if (arr[i]>v){

                swap(arr,i,gt-1);
                gt--;
            }else
                i++;
        }
        swap(arr,l,lt);

        threeSort(arr,l,lt-1);
        threeSort(arr,gt,r);

    }



    public void swap(int arr[],int i,int j){

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {

        mht m = new mht();
        int a[] = {2,5,9,1,3,10,7,6,8,4};

        System.out.print("排序前：");
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }

        System.out.println();
        m.kuaipai(a);

        System.out.print("排序后：");
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+"  ");
        }
    }
}
